2025 iThome 鐵人賽

DAY 10

Software Development

數學老師學函數式程式設計 - 以fp-ts啟航系列第 10 篇

Day 10. FP程式範例 - 淺嚐密碼學(Cipher)

17th鐵人賽密碼學 rsa 擴展歐基里德演算法

olddunk

2025-09-10 07:47:56

111 瀏覽

分享至

一直很喜歡密碼學的內容，因為用到了許多高中數學的知識，今天來用遞迴函數及函數的合成實作一個密碼學著名的RSA演算法，在實作這個演算法之前，我們先介紹一些高中數學的基本知識。

輾轉相除法

以前在教高中生遞迴函數的時候，總是會教下面這個例子：
a， b兩個是正整數，且 a大於 b，求 a和 b的最大公因數。
這個問題的最佳解法是歐基里德演算法(Euclid's Algorithm)，也就是我們熟悉的「輾轉相除法」。

歐基里德演算法(Euclid's Algorithm)原理：

被除數與除數的最大公因數，等於除數與餘數的最大公因數。

這是一個典型的遞迴問題，因為我們可以將求a和b的最大公因數，轉換成求 b和 a除以 b的餘數的最大公因數。而寫一個typescript的函數，只要需要二行就可以解決。

const gcd = ( divdent: number, divisor: number): number =>
  divisor == 0 ?  divdentent : gcd(divisor,  divdentent % divisor);

我們可以將這個問題稍做推廣，可以得到擴展歐基里德演算法(Extended Euclid's Algorithm)，這個演算法可以求出 a和 b的最大公因數，以及a和b的線性組合表示其最大公因，寫出數學式就是：

對所有的 a, b ∈ Z, 必然存在 x, y ∈ Z, 使得
gcd(a, b) = ax + by

這個問題等同於求一個二元一次不定方程式整數解：

ax + by = 1, 其中 a, b 滿足 gcd(a, b) = 1

這是以前高中數學常解的一個題目，它的作法如下：

ax + by = 1 ⇒ ax = 1 - by ⇒ ax ≡ 1 (mod b)

例如:

35x + 24y = 1

首先，我們用輾轉相除法來計算 35 和 24 的最大公因數 gcd。

35 ÷ 24 = 1 餘 11
所以， 35 = 24 × 1 + 11。
24 ÷ 11 = 2 餘 2
所以， 24 = 11 × 2 + 2。
11 ÷ 2 = 5 餘 1
所以， 11 = 2 × 5 + 1。
2 ÷ 1 = 2 餘 0
所以， 2 = 1 × 2 + 0。

當餘數為 0 時，最後一個非零餘數就是最大公因數。因此，gcd(35, 24) = 1。

步驟 2：回推求解

既然 gcd(35, 24) = 1，我們可以通過回推來找到滿足 24x + 35y = 1 的整數解。

從步驟 1 的計算中，我們有：

1 = 11 - 2 × 5
從 11 = 35 - 24 × 1，代入得：
1 = (35 - 24 × 1) - 2 × 5

從 2 = 24 - 11 × 2，代入得：
1 = 11 - (24 - 11 × 2) × 5
化簡後：
1 = 11 × 11 - 24 × 5

再次代入 11 = 35 - 24 × 1：
1 = (35 - 24 × 1) × 11 - 24 × 5
化簡後：
1 = 35 × 11 - 24 × 16

因此，我們得到一個特解：
x = -11, y = -16

步驟 3：通解

方程 24x + 35y = 1 的通解為：
x = -16 + 35k
y = 11 - 24k
其中 k 為任意整數。

最終答案

滿足 35x + 24y = 1 的整數解為：

(x, y) = (11 - 24k, -16 + 35k)，其中 k ∈ ℤ

如果採程序性的想法將上述的回推程序寫成程式，會顯得十分複雜，如果我們可以找到它的遞迴關係，再將它寫成遞迴函數，這樣的寫法會輕鬆容易許多。

從方程式 ax₀ + by₀ = gcd(a, b) 出發，

我們以 a 為被除數， b 為除數，得到餘數 r，依據除法原理得到

a = qb + r，

由於 gcd(a, b) = gcd(b, r) = bx₁ + ry₁
，
ax₀ + by₀ = bx₁ + ry₁，

用 qb + r 代入 a 得到 (qb + r)x₀ + by₀ = bx₁ + ry₁ 展開得

qbx₀ + rx₀ + by₀ = bx₁ + ry₁

b(qx₀ + y₀) + rx₀ = bx₁ + ry₁，比較係數得到

qx₀ + y₀ = x₁， x₀ = y₁

最後得到遞迴關係式 x₀ = y₁ 且 y₀ = x₁ - qy₁

而基礎條件為當 b = 0 時，此時 gcd(a, b) = a，

二元一次不定方程式則為 ax + 0 = a，得到 x = 1， y = 0

根據這個遞迴關係，我們可以寫出下面的程式碼：

const quotient = (divident: number, divisor: number) => {
  const remainder = divident % divisor;
  return (divident - remainder) / divisor;
};

const extGcd = (a: number, b: number) => {
  if (b === 0) return [1, 0];
  const [x, y] = extGcd(b, a % b);
  return [y, x - quotient(a, b) * y];
};

const gcdTest = gcd(35, 24) // 1
const extGcdTest = extGcd(35, 24); // [11, -16]

同餘代數

設 a, b 是整數， n 是一個正整數，如果 a - b 除以 n 的餘數相同，則我們我們稱 a 和 b 在模 n 下同餘，記作

a ≡ b (mod n)

舉例來說，

17 ÷ 5 餘 2，所以 17 ≡ 2 (mod 5)
(38 - 11) ÷ 9 餘 0，所以 38 ≡ 11 (mod 9)

換一個角度來說，在模 n 的前提之下，我們討論的集合只有A = {0, 1, 2, 3, ..., n - 1}。

加法和減法

以模 n 來說，我們定義集合 A 的乘法為兩數相乘後除以 n 的餘數，在這樣的加法定義下，很容易可以計算加法反元素(相反數)，因此我們可以有減法。以模 7 來說，我們討論的集合便是 A = {0, 1, 2, 3, 4, 5, 6}，如果兩數相減的結果為負，則把它加上 7 ，因此我們依舊可以做移項的代數運算。

x + 5 ≡ 3 (mod 7) ⇒ x ≡ 3 - 5 (mod 7) ≡ 5 (mod 7)

乘法和除法

以模 n 來說，我們定義集合 A 的乘法為兩數相乘後除以 n 的餘數，在這樣的定義下，找乘法反元素(倒數)顯困難許多，而且未必然有倒數，所以也就不一定能做除法。以模 7 來說，我們要找一個數乘以 5 以後和 1 同餘，也就是

x × 5 ≡ 1 (mod 7)

要找出這個同餘方程式的方法第一直覺是從 A = {0，1, 2, 3, 4, 5, 6}中一個一個找，看那一個數滿足同餘方程式，A 集合中只有 7 個數，很快可以試出答案是 2 ，而且只有 2 可以滿足。

如果我們的模數 n 很大，這個方法顯然不切實際。我們從定義上看看這個同餘方程式的本質是什麼？依據定義，　(x × 5 - 1　) 除以 7 必須整除，也就是 (x × 5 - 1　) = 7 × y， y 是一個整數，我們得到下面的方程式

5x - 7y = 1， x, y 是整數。

這時候，我們的擴展歐基里德演算法便可以派上場了，而這個整數方程式有解是因為 5 和 7 必須互質。在一般的情況下，一個數 a 在模 n 的情形下有倒數的充分必要條件是 a 和 n 互質。

模同餘消去律

如果 ca ≡ cb (mod n) 且 c 與 n 互質，則 a ≡ b (mod n)

同餘方程式無法像一般方程式任意消去公因數，這是因為模倒數未必存在，而模倒數存在充分必要條件是 c 和 n 互質。

RSA演算法

接下來，我們來介紹RSA演算法的原理，這個演算法是由三位數學家Rivest、Shamir和Adleman在1977年提出的，因此得名為RSA演算法。RSA演算法是一種非對稱加密演算法，所謂非對稱加密演算法就是加密和解密使用兩個不同的密鑰：公鑰和私鑰，公鑰用於加密數據，而私鑰用於解密數據。這種演算法最主要用的是數論中的歐拉定理。

在說明歐拉定理之前我們先看看下面指數的同餘方程式是否有解？

aᵐ ≡ 1 (mod 7)

下面的表格列出了所有的答案

a	1	2	3	4	5	6
m	1	3	6	3	6	2

這個表透露了一些訊息， m 都是 6 的因數，也就是 a⁶ ≡ 1 (mod 7)，這個就是費馬小定理。

費馬小定理

若p是一質數，且 a 不是 p 的倍數，則 aᵖ⁻¹ ≡ 1 (mod p) 或 aᵖ ≡ a (mod p)

我們以 p = 7 為例簡單的說一下這個定理的證明，集合{a, 2a, 3a, 4a, 5a, 6a}必等於{1, 2, 3, 4, 5, 6}，因此我們把兩個集合中的6個數相乘可得，6! × a⁶ ≡ 6!(消去律)，所以 a⁶ ≡ 1 (mod 7)。

歐拉定理是費馬小定理的推廣，它說我們的模可以是任何正整數 n ，而指數只要是 n 的歐拉函數φ(n)即可。

歐拉定理：

$a^{φ(n)}$ ≡ 1 (mod n)，
其中 φ(n) 是歐拉函數，表示小於 n 且與 n 互質的正整數的個數。

歐拉函數的計算公式：
φ(n) = n × ∏ (1 - 1/p) ，對所有n的質因數 p

舉例來說，n = 33 = 3× 11，31 的質因數只有 3 和 11 ，所以小於 33 且與 33 互質的正整數有

33 × (1 - 1 / 3) × (1 - 1 / 11) = (3 - 1) × (11 - 1)

共 20 個， φ(33) = 20，所以 a²⁰ ≡ 1 mod 33，如果 a 和 33 互質；也就是說，a²¹ 除以 33 的餘數是 a。

以上面的例子來說，我們希望找到一組數字(e, d)，e × d = 20 × k + 1，那麼對任整數 m ， mᵉᵈ = m²⁰ᵏ × m = m，數字組(e, d)我們可以拿其中一個當公鑰，另一個當私鑰。

如果公鑰是 e，私鑰是 d，假設明文為 m，我們先計算 mᵉ
除以 n 的餘數得到密文 c，這是加密的過程，得到密文的人再將密文 c的 d 次方除以 n 的餘數就可以得到明文 m，這個過程就是解密。要滿足這個過程， mᵉᵈ
≡ m (mod n) 必須成立，也就是說 e × d ≡ 1 mod φ(n)

至於如何得到 d 和 e 呢？因為公鑰 e 可以隨便選一個和33互質的整數，問題就只剩下找私鑰 d 了，聰明的你猜到如何計算 d 了嗎？

沒錯，就是擴展歐基里德演算法，因為同餘方程式　

e × d ≡ 1 mod φ(n)

可以寫成

e × d - k × φ(n) = 1，其中 k 是一個整數。

求出 e 和 φ(n) 的最大公因數，如果 e 和 φ(n) 互質，則 e 和 φ(n) 的最大公因數是 1，這時候我們可以利用擴展歐基里德演算法求出 e 和 φ(n) 的線性組合，使得 e × d ≡ 1 mod φ(n) ，這樣我們就可以得到 d 了。

這邊很容易弄混的地方在於有二個模，一個是 n ，一個是 φ(n)，

mᵉᵈ ≡ m (mod n)

e × d ≡ 1 (mod φ(n))

這個過程就好像是在走一個單向入口的旋轉門，我們可以從入口進去，但是無法反向從入口出來，只能繼續旋轉，一直轉到正確的格數，才能從出口出來，這種函數我們稱為「陷門單向函數」（trapdoor one-way function），這種函數的反函數很難求，但是正函數很容易計算。

接下來我們來實作RSA演算法。
兩質數相乘的歐拉函數：

const euler = (p: number, q: number): number => (p - 1) * (q - 1);

模次方同餘函數：

const modPower =
  (base: number) =>
  (power: number) =>
  (mod: number): number =>
    power === 0 ? 1 : (base * modPower(base)(power - 1)(mod)) % mod;

這兩個函數我們也都使用了遞迴函數，今天四個基本運算的函數都用遞迴函數完成，你有沒有感受到遞迴函數的威力。

最後，我們來進行加密和解密函數，其實加密和解密函數就是模次方同餘函數，只是加密我們使用公鑰，解密我們使用私鑰。

const generateCode =
  ([e, n]: [number, number]) =>
  (m: number): number =>
    modOfPower(m)(e)(n);

const encode = generateCode(publicKey);
const decode = generateCode(privateKey);

最後，我們把所有過程串成一個encryt函數，這個函數可以輸入一串字串，然後將字串轉成數字，再將數字加密，最後將加密後的數字轉成字串，這樣我們就可以將字串加密成密文。

import { pipe } from 'fp-ts/function'
const crypt = (key: Key) => (text: string) =>
  pipe(
    text.split(''), // 字串轉為字元陣列
    map((s) => s.charCodeAt(0)), // 字元轉換為unicode
    map(generateCode(key)), // 根據key產生密文或明文
    map((x) => String.fromCharCode(x)) // 將unicode轉為字元
  ).join(''); // 將字元陣列轉為字串

我們用以下的明文做測試

const [publicKey, privateKey] = generateKey(43, 59, 13);
const plainText =
  'The difference between the ord values of two characters is equal to how far apart they arethe Unicode table.';

const cipherText = crypt(publicKey)(plainText); // ʚ̣Ծ؈Å̚ɽɽԾ֭ԾَȕԾ؈פԾࡕʊԾԾَ؈ࡕ̣Ծ؈ٰ֭Å؈ݠؐ؎ίԾ৐؈ٰɽ؈ࡕʊٰ؈ụ֭̏ؐؐȕࡕԾ֭৐؈̚৐؈Ծˣίؐ؎؈ࡕٰ؈ٰ̣ʊ؈ɽ֭ؐ؈ؐΥ֭ؐࡕ؈ࡕ̣Ծۈ؈֭ؐԾࡕ̣Ծ؈Ӟَ̚ȕٰÅԾ؈ࡕؐפ؎Ծ߱
const originText = crypt(privateKey)(cipherText); // The difference between the ord values of two characters is equal to how far apart they arethe Unicode table.

優化模指數計算

原來modPower函數的計算非常直接，遇到次方太大的情形，number型別會溢位，所以將modpower進行優化。優化分成兩個部分。第一部分是兩數相乘再取模變成兩數取模再相乘，然後再取模，這樣可以馬上讓相乘的數不致於太大；第二部分則是指數次方採每次折半，一直遞廻，這樣不但可以避免溢位，也可以加快計算速度。

密碼學中計算的次方和所選的質數都非常大，如此才無法破解，即使選用BigInt型別也會溢位，這裏只是教學說明原理，所選數字都不是很大。

const isEven = (x: number) => (x % 2 === 0 ? true : false);

const productMod = (a: number, b: number, mod: number) =>
  mod === 1 ? 0 : ((a % mod) * (b % mod)) % mod;

const modOfPowerHalf = (base: number) => (power: number) => (mod: number) => {
  // 基礎情形
  if (mod === 1) return 0;
  if (power === 0) return 1;
  if (power === 1) return base % mod;
  const halfPower = isEven(power) ? power / 2 : (power - 1) / 2;
  const halfModOfPower = modOfPowerHalf(base)(halfPower)(mod);
  const halfModOfPowerProduct = productMod(halfModOfPower, halfModOfPower, mod);
  return isEven(power)
    ? halfModOfPowerProduct
    : productMod(halfModOfPowerProduct, base, mod);
};

今日小結

輾轉相除法(擴展歐基里德演算法)在密碼學或數論都佔有相當重要的角色，無論是證明或計算上也都舉足輕重，很可惜的是現今的高中教材已經將這一部分的內容移除，藉著鐵人賽的機會再將這一段複習一番。今天雖然已將RSA演算法的理論和實作部分大體的流程介紹過，但一些證明不是很嚴謹，請見諒。透過證明，可以對性質有更深入的了解，也更能清楚定理成立關鍵之所在，一般人都害怕證明，殊不知，學習定理的證明是讓自己數學直觀進步最好的方法。

在演算法的部分，還有很多的細節可以深究，例如質數的產生，都還有很大的學問，有興趣的朋友可以自行探討。

今天的內容頗為燒惱，雖花了不少時間整理，但覺得內容還可以再更好一些，但由於時間緊迫，只好就此罷手，今天的內容就到此為止，明天再見。